The invention relates generally to computer memory systems, and more particularly to a content addressable memory system, method and computer program product for accessing and managing data in the content addressable memory system.
Memory hierarchy and virtual memory models used in today's computers typically use addressing schemes where memory content is accessed by location in physical and virtual address spaces, i.e., data is uniquely referenced by the location where it resides. While virtual addressing allows data to be accessed and manipulated without being concerned with the actual underlying physical location and memory address of the data, it only does so in large units of contiguous memory locations like memory pages.
In general, data representations based on address contiguity such as arrays are often used by software applications because they involve less intermediate references to data and tend to be simpler. Spatial locality of reference has thus become an inherent consideration for efficient software implementations. Efforts by programmers to increase locality of reference in applications are now a common optimization strategy. Such an optimization is usually effective; however, in some situations it could introduce undue constraints and overheads in memory usage. For example, it is often difficult to predict the exact size of a contiguous memory space needed or to select the most efficient data lookup structures ahead of time. This is especially true in large applications which require a high amount of flexibility and comprise several independently built software components that are dynamically integrated. Software optimization based on locality of reference may therefore lead to fragmentation, wasted space and even extra processing when software developer choices turn out to be inappropriate.
Content addressable memory (CAM) systems can address this problem by virtue of fast parallel key-value lookup and range matching capabilities. In particular a general purpose virtual content addressable memory system provides an attractive alternative to traditional location based addressing which suffers from the above described restriction of uni-dimensional spatial locality constraints.
However, CAM/TCAM (ternary content addressable memory) systems lack support for ordered access, such as locating the next element in a hierarchy or iterating through a sequence, a key requirement for many applications and data structures. In network routers using TCAMs, this issue is addressed by storing keys in a desired physical order and employing a priority encoder that selects the first match in a range, as stored in the lowest physical address. This approach is unsuitable for a general purpose virtual content addressable memory system, where storing all TCAM entries sorted in physical order is not only impractical but also defeats the key strengths of content addressable models (i.e. their flexibility, freedom from spatial contiguity constraints and support for multiple key dimensions).
The above drawbacks of existing solutions motivate a need for an efficient content addressable memory system that can support ordered sequences and a method for using the memory system to traverse these sequences without losing the benefits offered by pure content addressing.